package AI;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/7/6 22:03
 */
public class Te {
    //写出一个冒泡排序
    public static void main(String[] args) {
        int[] arr = {1, 3, 2, 5, 4};
        bubbleSort(arr);
        for (int i : arr) {
            System.out.println(i);
        }
    }

    //冒泡排序
    public static void bubbleSort(int[] arr) {
        int len = arr.length;
        for (int i = 0; i < len - 1; i++) {
            //每次都从第一个开始比较，所以j=0
            for (int j = 0; j < len - 1 - i; j++) {
                //如果前面的比后面的大，就交换位置
                if (arr[j] > arr[j + 1]) {
                    //交换位置
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    // 分析上面的冒泡排序的时间复杂度
    // 1. 最好的情况，数组本身就是有序的，那么只需要比较n-1次，时间复杂度为O(n)
    // 2. 最坏的情况，数组本身是逆序的，那么需要比较n-1次，时间复杂度为O(n^2)
    // 3. 平均情况，时间复杂度为O(n^2)
    // 4. 空间复杂度为O(1)
    // 5. 稳定性：冒泡排序是稳定的排序算法，因为在比较的时候，如果相等的时候不交换位置，那么就是稳定的排序算法
    // 6. 冒泡排序是原地排序算法，因为不需要额外的空间，只需要一个临时变量就可以了

    // 冒泡排序的优化
    // 1. 如果在某一次比较中，没有发生交换，那么说明数组已经有序了，就不需要再继续比较了，直接退出循环即可
    // 2. 如果数组的后面一部分已经有序了，那么就不需要再比较了，直接从后面有序的那个位置开始比较即可
    //给出优化的代码
    public static void bubbleSort2(int[] arr) {
        int len = arr.length;
        //记录最后一次交换的位置
        int lastExchangeIndex = 0;
        //无序数组的边界，每次比较只需要比到这里为止
        int sortBorder = len - 1;
        for (int i = 0; i < len - 1; i++) {
            //提前退出冒泡循环的标志位
            boolean flag = true;
            //每次都从第一个开始比较，所以j=0
            for (int j = 0; j < sortBorder; j++) {
                //如果前面的比后面的大，就交换位置
                if (arr[j] > arr[j + 1]) {
                    //交换位置
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    //因为有元素进行交换，所以不是有序的，标志位为false
                    flag = false;
                    //把无序数组的边界更新为最后一次交换元素的位置
                    lastExchangeIndex = j;
                }
            }
            //如果没有元素进行交换，说明已经有序了，就直接退出循环
            if (flag) {
                break;
            }
            //把无序数组的边界更新为最后一次交换元素的位置
            sortBorder = lastExchangeIndex;
        }
    }

    // 斐波那契递归函数
    public int recurison(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        // 实现一个向上取整
        int a = 10, b = 8;
        int c = (a + b - 1) / b;

        // 递归调用
        return recurison(n - 1) + recurison(n - 2);
    }

    // 实现一个二分查找
    public int binSearch(int nums[], int val) {
        int low = 0, r = nums.length - 1;
        while (low < r) {
            int mid = low + r >> 1;
            if (nums[mid] >= val) r = mid;
            else low = mid + 1;
        }
        return low;
    }

    // 实现一个快速排序
    public void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // 找寻基准数据的正确索引
            int index = getIndex(arr, low, high);
            // 进行迭代对index之前和之后的数组进行相同的操作使整个数组变成有序
            quickSort(arr, low, index - 1);
            quickSort(arr, index + 1, high);
        }
    }

    // 实现getIndex
    public int getIndex(int[] arr, int low, int high) {
        // 基准数据
        int tmp = arr[low];
        while (low < high) {
            // 当队尾的元素大于等于基准数据时,向前挪动high指针
            while (low < high && arr[high] >= tmp) {
                high--;
            }
            // 如果队尾元素小于tmp了,需要将其赋值给low
            arr[low] = arr[high];
            // 当队首元素小于等于tmp时,向前挪动low指针
            while (low < high && arr[low] <= tmp) {
                low++;
            }
            // 当队首元素大于tmp时,需要将其赋值给high
            arr[high] = arr[low];
        }
        // 跳出循环时low和high相等,此时的low或high就是tmp的正确索引位置
        // 将tmp赋值给arr[low]
        arr[low] = tmp;
        return low; // 返回tmp的正确位置
    }

    // 测试上面的快速排序的正确性，使用冒泡排序进行验证
    //使用单元测试，并分别展示冒泡排序和快速排序的排序后的数组
    @Test
    public void test() {
        int[] arr = {1, 3, 2, 5, 4};
        int[] arr2 = {1, 3, 2, 5, 4};
        bubbleSort(arr);
        quickSort(arr2, 0, arr2.length - 1);
        System.out.println(Arrays.toString(arr));
        System.out.println(Arrays.toString(arr2));
    }

    // 求和计算使用递归，并给出注释
    public static int sum(int[] arr, int n) {
        // 递归的终止条件
        if (n == 1) {
            return arr[0];
        }
        // 把原问题转化成更小的问题
        return sum(arr, n - 1) + arr[n - 1];

    }
    // 实现一个 累加器
    /*
     一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。
     */

}

